package linklist;

/*
 *@description
 *@author hkfan
 *@version 1.0
 *@create 2025/6/9 16:28
 */
public class LeetCode_92 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //1. 添加头节点
        ListNode tempHead = new ListNode(0, head);
        //2. 找到left-1和right+1节点
        ListNode nodeA = findNode(tempHead,left-1);
        ListNode nodeB = findNode(tempHead,right+1);
        //3. 反转
        ListNode[] res = reverse(nodeA.next,right-left+1);
        //4. 重新合并
        nodeA.next=res[0];
        res[1].next = nodeB;
        return tempHead.next;
    }

    private ListNode[] reverse(ListNode start, int size) {
        ListNode p = start,q = start.next;
        ListNode[] res = new ListNode[]{null,p};
        int count = 1;
        while (count<size){
            ListNode temp = q.next;
            q.next = p;
            p=q;
            q=temp;
            count++;
        }
        res[0]=p;
        return res;
    }

    private ListNode findNode(ListNode head, int i) {
        int j=0;
        while (j<i){
            head=head.next;
            j++;
        }
        return head;
    }
}
